//
// Created by DengLibin on 2019/1/11 0011.
//

#include <iostream>
using namespace std;

/**
 * 合并两个有序链表为一个新的有序链表
 */
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

//循环实现
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode * temp1 = l1;
    ListNode * temp2 = l2;

    ListNode * headNode = NULL; //头节点
    ListNode * temp3 = NULL; //游标指针
        while (temp1 != NULL || temp2 != NULL){
             ListNode * nextNode = new ListNode(0); //创建节点
             if(temp3 == NULL){ //没有头结点
                 temp3 = nextNode; //作为头节点
                 headNode = temp3;
             }else{
                 temp3->next = nextNode; //有头节点作为下一个节点
                 temp3 = nextNode; //指向该节点
             }

             //判断然取值
        if(temp1 != NULL){
            if(temp2 ==NULL || temp1->val < temp2->val){
                temp3->val = temp1->val;
                temp1 = temp1->next;
            }else{
                temp3->val = temp2->val;
                temp2 = temp2->next;
            }
        }else{
                temp3->val = temp2->val;
                temp2 = temp2->next;
        }
    }
    return headNode;
}
//递归实现
ListNode* mergeTwoLists2(ListNode* l1, ListNode* l2) {
    if(l1 == NULL){
        return l2;
    }
    if(l2 == NULL){
        return  l1;
    }
    ListNode * resNode = NULL;
    if(l1->val < l2->val){
        resNode = l1;
        resNode->next = mergeTwoLists2(l1->next, l2);
    }else{
        resNode = l2;
        resNode->next = mergeTwoLists2(l1, l2->next);
    }
    return resNode;
}

int main56(){
    ListNode l1(1);
    ListNode l2(2);
    ListNode l3(4);
    l1.next = &l2;
    l2.next = &l3;

    ListNode l4(1);
    ListNode l5(3);
    ListNode l6(4);
    l4.next = &l5;
    l5.next = &l6;
    ListNode* head =  mergeTwoLists2(&l1, &l4);
    ListNode * temp = head;
    while(temp != NULL){
        cout <<temp->val<<",";
        temp = temp->next;
    }

    return 0;
}